package leetcode;

import java.util.ArrayList;
import java.util.List;

public class MinHeightTree310 {
    public static void main(String[] args) {
//        System.out.println(findMinHeightTrees(4, new int[][]{{1,0},{1,2},{1,3}}));
        System.out.println(findMinHeightTrees(6, new int[][]{{3,0},{3,1},{3,2},{3,4},{5,4}}));
    }
    public static List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> root = new ArrayList<>();
        int h = Integer.MAX_VALUE;
        int[] used = new int[n];
        for (int i = 0; i < n; i++) {
            int tt = dfs(i, edges, used, 0);
            System.out.println(tt);
            if(tt == h)
            {
                root.add(i);
                continue;
            }
            if(tt < h);
            {
                root.clear();
                h = tt;
                root.add(i);
            }
        }
        return root;
    }
    public static int dfs(int r, int[][] edges, int[] used, int height){
        for (int i = 0; i < edges.length; i++) {
            if(used[r] == 1)
               break;
            if(r == edges[i][0] && used[r] == 0)
            {
                used[r] = 1;
                height++;
                dfs(edges[i][1], edges, used, height);
                used[r] = 0;
            }
            if(r == edges[i][1] && used[r] == 0)
            {
                used[r] = 1;
                height++;
                dfs(edges[i][0], edges, used, height);
                used[r] = 0;
            }
        }
        return height;
    }
}

/*
n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
 */
